#include <iostream>
using namespace std;
void Backtrack(int n,int t,int **M,int count,int &sum,int *v)
{
	int i,j,temp=count;
	for(i=0;i<2;i++)
	{
		v[t]=i;
		M[t][1]=i;
		count+=i;
		for(j=2;j<=t;j++)
		{
			M[t][j]=M[t][j-1]^M[t-1][j-1];
			count+=M[t][j];
		}
		if(count==n*(n+1)/4&&t==n)
		{
			sum++;
			cout<<endl<<sum<<":"<<endl;
			for(int k=1;k<=n;k++)
				cout<<v[k];
			return;
		}
		else
			if(t<n&&count<(n*(n+1)/4)&&(t*(t+1)/2-count)<(n*(n+1)/4))
				Backtrack(n,t+1,M,count,sum,v);
		count=temp;
	}
}
void main()
{
	int n;
	int count=0;
	int sum=0;
	cout<<"please input the number"<<endl;
	cin>>n;
	int **M=new int *[n+1];
	int *v=new int[n+1];

	if(n*(n-1)%4!=0)
	{
		cout<<"sum is"<<0<<endl;
	}
	for(int i=0;i<=n;i++)
	{
		M[i]=new int[n+1];
	}

	Backtrack(n,1,M,count,sum,v);
	cout<<"sum is"<<sum<<endl;
}
